МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ ЛЬВІВСЬКА ПОЛІТЕХНІКА ” Кафедра ЕОМ Розрахункова робота на тему " Динамічні структури даних " з дисципліни " Обчислювальний практикум " Варіант №7  ЗМІСТ 1. ТЕОРЕТИЧНА ЧАСТИНА 3 1.1. Абстрактний тип даних (АТД, ADT) 3 1.2. Стек (Stack) 3 1.3. Черга (Queue) 3 1.4. Список (List) 4 1.5. Дерево (Tree) 5 2. ПОБУДОВА АТД 7 2.1. Абстрактний тип даних «Стек» 7 2.1.1. Реалізація стеку 7 2.1.2. Тестова програма 8 2.1.3. Результат тестування 8 2.2. Абстрактний тип даних «Черга» 9 2.2.1. Реалізація черги 9 2.2.2. Тестова програма 10 2.2.3. Результат тестування 11 2.3. Абстрактний тип даних «Список» 12 2.3.1. Реалізація списку 12 2.3.2. Тестова програма 14 2.3.3. Результат тестування 14 2.4. Абстрактний тип даних «Дерево» 15 2.4.1. Реалізація дерева 15 2.4.2. Тестова програма 17 2.4.3. Результат тестування 17 3. ЗАСТОСУВАННЯ АТД 18 3.1. Завдання 1 18 3.1.1. Опис алгоритму 18 3.1.2. Результат виконання програми 18 3.1.3. Блок-схема алгоритму 19 3.2. Завдання 2 21 3.2.1. Опис алгоритму 21 3.2.2. Результат виконання програми 21 3.2.3. Блок-схема алгоритму 22 3.3. Завдання 3 24 3.3.1. Опис алгоритму 24 3.3.2. Результат виконання програми 24 3.3.3. Блок-схема алгоритму 24 3.4. Завдання 4 26 3.4.1. Опис алгоритму 26 3.4.2. Результат виконання програми 26 3.4.3. Блок-схема алгоритму 27 ВИСНОВКИ 29 СПИСОК ЛІТЕРАТУРИ 30 ДОДАТОК А. КОД ПРОГРАМИ ДО ЗАВДАННЯ 1 31 ДОДАТОК Б. КОД ПРОГРАМИ ДО ЗАВДАННЯ 2 32 ДОДАТОК В. КОД ПРОГРАМИ ДО ЗАВДАННЯ 3 33 ДОДАТОК Г. КОД ПРОГРАМИ ДО ЗАВДАННЯ 4 37 ТЕОРЕТИЧНА ЧАСТИНА Абстрактний тип даних (АТД, ADT) Абстрактний тип даних – математична модель із сукупністю операторів, визначених в рамках цієї моделі. Простим прикладом можуть служити множини цілих чисел з операторами об’єднання, перетину та різниці множин. В моделі АТД оператори можуть мати операндами не лише дані, визначені цим АТД, але і дані інших типів: стандартних типів, визначених мовою програмування чи визначених в інших АТД. АТД можна розглядати як узагальнення простих типів даних. Він інкапсулює типи даних в тому сенсі, що визначення типу і всі оператори, виконувані над даними цього типу, поміщаються в один розділ програми. Якщо необхідно змінити реалізацію АТД, ми знаємо, де знайти і що змінити в одному невеликому розділі програми. Термін «реалізація АТД» передбачає наступне: переведення в оператори мови програмування оголошень, що визначають змінні цього абстрактного типу даних, плюс процедури для кожного оператора, виконуваного над об’єктами АТД. Реалізація залежить від структури даних, що представляє АТД. Кожна з них будується на основі базових типів даних застосовуваної мови програмування, використовуючи доступі засоби структурування. Різницяміжабстрактними типами даних і структурами даних, які реалізують абстрактні типи, можна пояснити на наступному прикладі. Абстрактний тип данихсписок може бути реалізований за допомогою масиву або лінійного списку, з використанням різних методів динамічного виділення пам'яті. Однак кожна реалізація визначає один і той же набір функцій, який повинен працювати однаково (по результату, а не по швидкості) для всіх реалізацій. Абстрактнітипиданихдозволяютьдосягтимодульності програмнихпродуктів і матикількаальтернативнихвзаємозаміннихреалізаційокремого модуля. Стек (Stack) З англ. stack - стопка - структура даних, в якій доступ до елементів організований за принципом LIFO (англ. last in - firstout , "Останнім прийшов - першим вийшов"). Найчастіше принцип роботи стека порівнюють зі стопкою тарілок: щоб взяти другу зверху, потрібно зняти верхню. В цифровому обчислювальному комплексі стек називається магазином - по аналогії з магазином у вогнепальній зброї (стрільба почнеться з патрона, зарядженого останнім). Таблиця 1.2.1. Основні операції над стеком Операція Дія  empty() Повертає true, якщо стек порожній, і false у противному випадку  sіze() Повертає розмір стека  pop() Видаляє вершину стека  top() Повертає значення вершини стека  ...